package algorithmlearn.sort;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] array = {11,22,334,231,433,11,334,22,41,57,60};
        int[] ints = shellSort(array);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + "  ");
        }
    }

    public static int[] shellSort(int[] array){
        if (array == null || array.length < 2) {
            return null;
        }
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0){
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                if(preIndex >= 0 && array[preIndex] > temp){
                    array[i] = array[preIndex];
                    array[preIndex] = temp;
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap = gap/2;
        }
        return array;
    }

}
